1. Field
The present invention relates to computers and computer networks. More particularly, the present invention relates to method and apparatus for worm detection and containment in the Internet Core.
2. Description of Related Art
Recent years have seen a sharp increase in Internet worms causing damage to millions of systems worldwide. Worms are automated programs that exploit vulnerabilities in computers connected to the network in order to gain control over them. Once they have successfully infected a system, they continue to search for new victims and can spread through the network on their own. Worse, each new epidemic has demonstrated increased speed, virulence or sophistication over its predecessor. While the Code Red worm took over fourteen hours to infect its vulnerable population in 2001, the Slammer worm, released some 18 months later, did the same in less than 10 minutes. More details can be found in D. Moore, V. Paxon, S. Savage, C. Shannon, S. Staniford, and N. Weaver “The Spread of the Sapphire/Slammer Worm”, IEEE Security and Privacy, 1(4), July 2003, and D. Moore, C. Shannon, and J. Brown “A Case Study on the Spread and Victims of an Internet Worm”, Proceeding of the ACM Internet Measurement Workshop, November 2002. The Code Red worm is thought to have infected roughly 360,000 hosts, while by some estimates, the Nimda worm compromised over two million. More details can be found in M. Erbschloe, Computer Economics VP Research Statement to Reuters News Service, November 2001. Unfortunately, current ability in 2005 to defend against these outbreaks is extremely poor and has not advanced significantly since the Code Red episode in mid-2001. In fact, the basic approach of detection, characterization and containment has not changed significantly over the last five years.
Typically, a new worm is detected in an ad-hoc fashion and its signature extracted to update the anti-virus and network filtering products. While such approaches are qualitatively sound, they are not quantitatively efficient. Manual signature extraction is an expensive procedure that takes hours or even days to complete. It requires isolating a new worm, decompiling it, looking for invariant code sequences and testing for signature uniqueness. However, recent simulations by Moore et al. suggest that to be effective, worm containment must react within sixty seconds. More details can be found in D. Moore, C. Shannon, G. Voelker, and S. Savage “Internet Quarantine: Requirements for Containing Self-Propagating Code,” Proceedings of the Infocom, April 2003.
With worms becoming ever complex and numerous, enterprise networks have been increasingly offloading the responsibility for worm detection and containment to the carrier networks. Enterprise networks are becoming more open and hence vulnerable to attacks as laptops and other portable interne devices traverse traditional perimeter defenses, traveling from place to place and network to network. Additionally, with mandated government regulations, customer privacy concerns and a lack of security knowledge within their IT departments, enterprise customers find securing their networks quite a daunting task. Thus, as enterprise customers realize that their traditional point solutions and perimeter defenses are becoming inadequate, they are shifting their security burden to carriers where it is more efficient and cost-effective.
The potential revenue opportunity for carriers to providing worm containment at the Internet core is huge, since it serves as an important brand differentiator to their services. Moreover, effective worm containment at the carrier to enterprise perimeter frees up resources that the carrier could use instead for carrying traffic for the plethora of bandwidth intensive applications such as multimedia that are in vogue. However, most worm detection algorithms designed so far have catered to the lower rate (100 Mbps to 1 Gbps) enterprise networks, solutions that are not scalable to the high data rate links which characterize the carrier networks (OC-12 up to OC-192).
It is well known that inspecting layer-7 content per packet to extract worm signatures is computation as well as memory intensive and hence, not scalable to the high data rate links such as those at the peering links across carriers. As a consequence, schemes proposed to work in the context of network carrier must consider this critical limitation. Moreover, it is not realistic to assume a carrier will have layer-7 visibility widely deployed through their entire network; usually the carrier will award this capability to only a few customers who pay for the specific service.
The various methods that have been proposed to identify new worms are divided into two major classes. The first class is based on content fingerprinting using layer-7 information. More details can be found in S. Singh, C. Estan, G. Varghese, and S. Savage “Automated Worm Fingerprinting,” Proceedings of the 6th ACM/USENIX Symposium on Operating System Design and Implementation (OSDI), December 2004, H. A. Kim and B. Karp, “Autograph: toward automated, distributed worm signature detection,” Proceedings of the 13th USENIX Symposium, August 2004, J. Newsome, B. Karp, and D. Song, “Polygraph: Automatically Generating Signatures for Polymorphic Worms,”, Proceedings of IEEE Security and Privacy Symposium, Oakland, Calif. USA, May 2005, and V. Karamcheti, D. Geiger, and Z. Kedem “Detecting Malicious Network Traffic using Inverse Distributions of Packet Contents”, ACM Sigcomm Workshop on Mining Network Data (MiNet), August 2005. The primary intuition underlying this class is that an ongoing worm propagation should manifest itself in the presence of higher than expected byte-level similarity among network packets: the similarity arises because of the unchanging portions of the worm packet payload, something expected to be present even in polymorphic or obfuscated worms (albeit spread out over the length of the packet). In particular, Earlybird tries to efficiently collect fingerprints of fixed size payload blocks from all the traffic crossing the network border and then checks the address dispersion for the content, reporting a worm when this dispersion is above a fixed threshold. More details can be found in S. Singh, C. Estan, G. Varghese, and S. Savage “Automated Worm Fingerprinting,” Proceedings of the 6th ACM/USENIX Symposium on Operating System Design and Implementation (OSDI), December 2004. Opposite approach is used in H. A. Kim and B. Karp, “Autograph: toward automated, distributed worm signature detection,” Proceedings of the 13th USENIX Symposium, August 2004, and J. Newsome, B. Karp, and D. Song, “Polygraph: Automatically Generating Signatures for Polymorphic Worms,”, Proceedings of IEEE Security and Privacy Symposium, Oakland, Calif. USA, May 2005. A pool of suspicious flows is created, using the number of unanswered inbound SYN packets (hint of a port scanning activity) as a tentative and imperfect indicator of suspect activity and then fingerprinting is applied to short variable length content blocks to identify content prevalence and report possible worms. All these approaches consider packet contents as a bag of substrings of either a fixed length, such as can be found in S. Singh, C. Estan, G. Varghese, and S. Savage “Automated Worm Fingerprinting,” Proceedings of the 6th ACM/USENIX Symposium on Operating System Design and Implementation (OSDI), December 2004, or a dynamic packet content-based length, such as can be found in H. A. Kim and B. Karp, “Autograph: toward automated, distributed worm signature detection,” Proceedings of the 13th USENIX Symposium, August 2004, and J. Newsome, B. Karp, and D. Song, “Polygraph: Automatically Generating Signatures for Polymorphic Worms,”, Proceedings of IEEE Security and Privacy Symposium, Oakland, Calif. USA, May 2005. In V. Karamcheti, D. Geiger, and Z. Kedem “Detecting Malicious Network Traffic using Inverse Distributions of Packet Contents”, ACM Sigcomm Workshop on Mining Network Data (MiNet), August 2005, the authors analyze the characteristics of the inverse distribution, I(f), which tracks for a given frequency f, the number of substrings that appear with that frequency and propose I(f) as a new discriminator for an earlier detection of worms. Although the metric used is interesting, the approach must still inspect the payload of all packets passing through the link.
In contrast to the aforementioned class of approaches based on layer-7 packet content analysis, the second class consists of techniques which identify network anomalies by examining the traffic distribution across a few features using layer-4 information. More details can be found in A. Wagner and B. Plattner “Entropy Based Worm and Anomaly Detection in Fast IP Networks”, IEEE 14-th International Workshop on Enabling Technologies: Infrastructures for Collaborative Enterprises (WET ICE), STCA security workshop, June 2005, A. Lakhina, M. Crovella, and C. Diot “Mining Anomalies Using Traffic Feature Distributions”, ACM Sigcomm, August 2005, K. Xu, Z. Zhang and S. Bhattacharyya “Profiling Internet Backbone Traffic: Behavior Models and Applications”, ACM Sigcomm, August 2005, and S. Wehner “Analyzing Worms and Network Traffic using Compression”, 2005, cs.CR/0504045. The primary intuition underlying these approaches is that a worm manifestation breaks the statistical characteristics of Internet traffic; worm traffic is more uniform or structured than normal traffic in some respects and more random in others. These approaches propose various techniques based primarily on information-theoretic measures such as Information entropy or Kolgomorov complexity as the statistics to represent the distribution of a traffic feature such as source and destination ip-addresses or port numbers. Thereafter, A. Lakhina, M. Crovella, and C. Diot “Mining Anomalies Using Traffic Feature Distributions”, ACM Sigcomm, August 2005 and K. Xu, Z. Zhang and S. Bhattacharyya “Profiling Internet Backbone Traffic: Behavior Models and Applications”, ACM Sigcomm, August 2005 propose techniques based on Principle Component Analysis (PCA) and Residual State Analysis (RSA) respectively, to establish complex relationships across the traffic features whereby flows are classified as either legitimate or malicious. However, these prior art approaches such as PCA and RSA, while robust, are primarily offline and hence not effective for worm containment at the high data rate links typical of the Internet core. A. Wagner and B. Plattner “Entropy Based Worm and Anomaly Detection in Fast IP Networks”, IEEE 14-th International Workshop on Enabling Technologies Infrastructures for Collaborative Enterprises (WET ICE), STCA security workshop, June 2005 identifies worm activity by detecting major changes in the compressibility characteristics of flow contents using Kolmogorov complexity. This method is also primarily offline and hence not effective for worm containment at the high data rate links typical of the Internet core.
Accordingly, there is a need for a method that is efficient in detecting worms while using only the layer-4 information that is easily extracted from core routers and also be scalable when layer-7 information is available. Further more there is a need for selecting a subset of network traffic data for analysis to bridge the gap between the two classes of approach in the prior art and bring together the characteristics of being deployable for real-time high data rate links and the efficiency and reliability of content fingerprinting techniques.